# 仅当列表是有序的时候，二分查找才管用。


# 官方代码  有问题
'''
def BinarySearch(list, item):
    low = 0
    high = len(list)-1

    while low <= high:
        mid = (low+high)
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None
my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 32, 24234, 23532, 3]
print(BinarySearch(my_list, 6))

'''


'''
list  对象列表
item  查找的对象
start 开始值
end   结束值
'''




import math
def BinarySearch(list, item, start, end):
    mid = math.ceil((start+end-1)/2)     # 向上取整  中间索引值
    if end-start <= 2:
        while start <= end:
            if list[start] == item:
                return start
            start += 1
        return None

    else:
        mid_v = list[mid]  # 中间值
        if item > mid_v:
            new_start = mid + 1
            return BinarySearch(list, item, new_start, end)
        elif mid_v == item:
            return mid
        else:
            new_end = mid - 1
            return BinarySearch(list, item, start, new_end)


my_list = range(100)
print(BinarySearch(my_list, 88, 0, len(my_list)-1))
